package pers.qianyu.month_202012.date_20201201;

/**
 * 712. 两个字符串的最小ASCII删除和
 * https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/
 *
 * @author mizzle rain
 * @date 2020-12-01 21:34
 */
public class MinimumDeleteSum {
    public int minimumDeleteSum(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        for (int i = 1; i < dp[0].length; i++) {
            dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);
        }
        for (int i = 1; i < dp.length; i++) {
            for (int k = 1; k < dp[0].length; k++) {
                if (s1.charAt(i - 1) == s2.charAt(k - 1)) {
                    dp[i][k] = dp[i - 1][k - 1];
                } else {
                    dp[i][k] = Math.min(dp[i - 1][k] + s1.charAt(i - 1),
                            dp[i][k - 1] + s2.charAt(k - 1));
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }
}
